// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _134

// canCompleteCircuit
// 如果gas的和小于cost的和，那么肯定就不可能绕环路行驶一周，否则有解
// 确定肯定有解之后，就需要判断解是什么
// 然后遍历数组，计算当前的油量，如果当前的油量小于0了，说明不能到达下一个加油站，那么则更新起始点为下一个加油站，重置当前油量为0
// 即，如果保证了肯定有解，那么找到一个起始点可以到下一个点，那么就肯定可以环路行驶一周回来。
func canCompleteCircuit(gas []int, cost []int) int {
	totalGas := 0
	totalCost := 0
	curGas := 0
	start := 0

	for i := 0; i < len(gas); i++ {
		totalGas += gas[i]
		totalCost += cost[i]
		curGas += gas[i] - cost[i]
		if curGas < 0 {
			start = i + 1
			curGas = 0
		}
	}

	if totalGas < totalCost {
		return -1
	}
	return start
}
